package suanfa.datastructure.tree;

import java.util.Queue;
import java.util.LinkedList;
import java.util.Stack;

class mynode{
    String name;
    mynode left,right;

    public mynode(String name){
        this.name=name;
        this.left=null;
        this.right=null;
    }

    public void setLeft(mynode left) {
        this.left = left;
    }

    public void setRight(mynode right) {
        this.right = right;
    }


    public void delenode(String name){
        //判断左子树是否删除
        if(this.left!=null&&this.left.name.equals(name)){
            System.out.println("删除左子树:"+name);
            this.left=null;
            return;
        }
        //判断右子树是否删除
        if(this.right!=null&&this.right.name.equals(name)){
            System.out.println("删除右子树:"+name);
            this.right=null;
            return;
        }

        if(this.left!=null){
            this.left.delenode(name);
        }
        if(this.right!=null){
            this.right.delenode(name);
        }
    }
    //前序遍历
    public void preorder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preorder();
        }
        if(this.right!=null){
            this.right.preorder();
        }
    }
    @Override
    public String toString(){
        return "Node{"+"name='"+name + '\"' + '}';
    }

}

class BinTree{
    mynode root;

    //广度优先遍历
    public void leveltravel(mynode node){
        Queue<mynode> queue=new LinkedList<>();
        queue.offer(node);
        while(!queue.isEmpty()){
            mynode re=queue.poll();
            System.out.println(re.name+"\t");
            if(re.left!=null){
                queue.offer(re.left);
            }
            if(re.right!=null){
                queue.offer(re.right);
            }
        }

    }

    public static void dfs(mynode root) {//深度优先遍历
        if (root == null) return;
        Stack<mynode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            mynode node = stack.pop();
            System.out.print(node.name + " ");  // 访问根节点

            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }




    public  BinTree(mynode r){
        this.root=r;
    }

    public void front(){
        if(this.root!=null){
            this.root.preorder();
        }else{
            System.out.println("根节点为空");
        }

    }


    public void delete(String name){
        if(root==null){
            System.out.println("空树,无法删除");
            return;
        }else if(root.name.equals(name)){
            root=null;
            System.out.println("已删除 "+name);
            return;
        }
        else{
            root.delenode(name);
        }

    }
}

public class Test {
    public static void main(String[] args) {
        mynode root=new mynode("root");
        mynode n1=new mynode("1");
        mynode n2=new mynode("2");
        mynode n3=new mynode("3");
        mynode n4=new mynode("4");
        mynode n5=new mynode("5");
        root.setLeft(n1);
        n1.setLeft(n2);
        n1.setRight(n3);
        root.setRight(n4);
        n4.setRight(n5);
        BinTree tree=new BinTree(root);
        System.out.println("广度优先遍历");
        tree.leveltravel(root);
        System.out.println("深度优先遍历");
        tree.dfs(root);

    }
}
